//给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
//输出：6
//解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
// 
//
// 示例 2： 
//
// 
//输入：nums = [1]
//输出：1
// 
//
// 示例 3： 
//
// 
//输入：nums = [0]
//输出：0
// 
//
// 示例 4： 
//
// 
//输入：nums = [-1]
//输出：-1
// 
//
// 示例 5： 
//
// 
//输入：nums = [-100000]
//输出：-100000
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 105 
// -104 <= nums[i] <= 104 
// 
//
// 
//
// 进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。 
// Related Topics 数组 分治 动态规划 
// 👍 4004 👎 0

package com.cute.leetcode.editor.cn;
public class MaximumSubarray {
    public static void main(String[] args) {
        Solution solution = new MaximumSubarray().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 我都不知道怎么想到这一点的（滚动变量求解，这居然是动态规划优化过的结果）
         * pre：连续区间和
         * res：结果
         * 遍历时根据当前值与当前值和pre的和进行比较，取最大的那一个作为pre
         * nums[i] 如果比nums[i]+pre都大的话直接将pre更新为nums[i]
         * 举例：[-2,1,-3,4,-1,2,1,-5,4]
         * 初始pre = -2 res = -2
         * i=1时，pre更新为Max(1,1-2)=1 res=1
         * i=2, pre=-2 res=1
         * i=3, pre=4 res=4
         * i=4, pre=3 res=4
         * i=5, pre=5 res=5
         * i=6, pre=6 res=6
         * i=7, pre=1 res=6
         * i=8, pre=5 res=6
         *
         */
        public int maxSubArray1(int[] nums) {
            int len = nums.length;
            if (len == 1) return nums[0];
            int pre = nums[0];
            int res = pre;
            for (int i = 1; i <len ; i++) {
                pre = Math.max(nums[i],nums[i]+pre);
                res = Math.max(res, pre);
            }
            return res;
        }

        //二刷和一刷一样
        public int maxSubArray2(int[] nums) {
            int len = nums.length;
            int pre = nums[0];
            int max = nums[0];
            //max存最大值，pre存连续和
            for (int i = 1; i<len; i++){
                if (pre <= 0) pre = nums[i];//这里表示要从新开始子序列了，重开条件要考虑全是负数的情况
                else pre += nums[i];
                max = Math.max(max, pre);
            }
            return max;
        }


        /**
         * 使用分治算法时可以分为左边，右边和跨中心三部分
         */
        public int maxSubArray(int[] nums) {
            return divideHelper(nums, 0, nums.length - 1);
        }

        // 这里是分的过程，求三部分的连续和，返回最大值
        private int divideHelper(int[] nums, int start, int end) {
            if (start == end) return nums[start];
            int mid = start + (end - start) / 2;
            int leftSum = divideHelper(nums, start, mid);
            int rightSum = divideHelper(nums, mid + 1, end);
            // 求穿过中心的最大值
            int midSum = countCross(nums, start, mid, end);
            return Math.max(Math.max(leftSum, rightSum), midSum);
        }

        // 跨中心求最大连续和时可以用贪心，然后相加
        private int countCross(int[] nums, int start, int mid, int end) {
            int leftSum = Integer.MIN_VALUE, rightSum = Integer.MIN_VALUE;
            int sum = 0;
            for (int i = mid; i >= start; i--) {
                sum += nums[i];
                leftSum = Math.max(leftSum, sum);
            }
            sum = 0;
            for (int i = mid + 1; i <= end; i++) {
                sum += nums[i];
                rightSum = Math.max(rightSum, sum);
            }
            return leftSum + rightSum;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}







































